"""
92. 反转链表 II
中等
相关标签
premium lock icon
相关企业
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。


示例 1：


输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]


提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

"""
from typing import Optional


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left==right:
            return head
        i = 1
        cur = head
        #  1 2 3 4 5 [2,4]
        ll = None #左左连接点 这里是1
        lr = None #左右连接点 这里是4 反转后ll和lr连接 1 - 4
        rl = None #
        rr = None

        pre = None
        while cur:
            if i==left:
                ll = pre
                rl = cur
            status = False

            tmp = None
            #处理反转部分
            while left <= i <= right:
                if i == right:
                    #当为反转的最后一个，记录连接点
                    rr = cur.next
                    lr = cur
                    status = True
                #反转
                next = cur.next #记录下一个索引
                cur.next = tmp #指向改为向左
                tmp = cur #下次循环的上一个
                cur = next #下次循环的当前
                i+=1
            if status:
                #反转结束，连接
                if ll:
                    ll.next = lr
                if rl:
                    rl.next = rr
                #防止第一位反转，以此头节点变了不再是初始的head
                if left == 1:
                    head = lr
                break
            pre = cur
            cur = cur.next
            i+=1
        return head

    def reverseBetween_res1(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left == right:
            return head

        # 创建虚拟头节点简化边界处理
        dummy = ListNode(0)
        dummy.next = head

        # 找到反转区间的前一个节点
        prev = dummy
        for _ in range(left - 1):
            prev = prev.next

        # 反转区间的第一个节点 也是最后一个元素，每次他都指向下一个要处理的系欸但
        curr = prev.next

        # 执行反转操作
        for _ in range(right - left):
            #每次把curr的后一个插入到反转的开头
            #记录下一节点信息
            next_node = curr.next
            #指向下次循环的预处理系欸但
            curr.next = next_node.next
            #下一节点放到第一位
            next_node.next = prev.next # 1> 2 >3 处理3时，完成 3>2
            prev.next = next_node # #1> 2 >3 处理3时，完成 1>3 最终 1>3>2

        return dummy.next


def print_list(head: Optional[ListNode]) -> None:
    """
    循环输出链表节点的值
    """
    current = head
    values = []
    while current:
        values.append(str(current.val))
        current = current.next
    print("->".join(values))

if __name__ == '__main__':
    # 测试用例1: head = [1,2,3,4,5], left = 2, right = 4
    # 构建链表 1->2->3->4->5
    head1 = ListNode(1)
    head1.next = ListNode(2)
    head1.next.next = ListNode(3)
    head1.next.next.next = ListNode(4)
    head1.next.next.next.next = ListNode(5)
    left1, right1 = 2, 4
    # 预期输出: [1,4,3,2,5]
    s = Solution()
    print_list(s.reverseBetween_res1(head1, 2, 4))
    #
    # # 测试用例2: head = [5], left = 1, right = 1
    # # 构建链表 5
    # head2 = ListNode(5)
    # left2, right2 = 1, 1
    # # 预期输出: [5]
    # print_list(s.reverseBetween(head2, 1, 1))
    #
    # head1 = ListNode(1)
    # head1.next = ListNode(2)
    # head1.next.next = ListNode(3)
    # head1.next.next.next = ListNode(4)
    # head1.next.next.next.next = ListNode(5)
    # left1, right1 = 2, 4
    # # 预期输出: [1,4,3,2,5]
    # s = Solution()
    # print_list(s.reverseBetween(head1, 3, 4))

    head1 = ListNode(3)
    head1.next = ListNode(5)
    s = Solution()
    print_list(s.reverseBetween(head1, 1, 2))